package me.seu.demo.algorithms.heap;

import java.io.*;

/**
 * Balanced k-way Sort Merge
 * Merge.java
 * Purpose: Takes an integer and a filename as command-line arguments.
 * The file contains initial runs created by CreateRuns program, and the integer is the k of the k-way merge.
 * Initial runs are read from the input file and distributed over k many temporary files for subsequent
 * merging using a heap. Output is a file containing all the data in sorrted order.
 * <p>
 * Authors: Elizabeth Macken and Sacha Raman
 */
public class Merge {
    public static void main(String[] args) {
        // Checking the correct number of arguments were passed and that the file passed is a .runs file
        if (args.length != 2 || !(args[1].endsWith(".runs"))) {
            System.out.println("ERROR - Correct usage: java Merge [integer] [filename.runs]");
            return;
        } else {
            try {
                // Getting the k-value passed and checking that it is at least 2
                int k = Integer.parseInt(args[0]);
                if (k < 2) {
                    System.out.println("ERROR - k-value must be greater than 1");
                    return;
                }
                // Creating a reader to read from the input file and an array of writers to print to files for sorting
                // 读文件流
                BufferedReader br = new BufferedReader(new FileReader(args[1]));
                // k-way写文件流
                PrintWriter[] writers = new PrintWriter[k];

                // Creating a file with the same name as the input file but replacing .runs with .sorted
                String filename = args[1].substring(0, args[1].length() - 5);

                // 最终要写入得排序文件
                File sortedFile = new File(filename + ".sorted");

                // Creating an array to store twice as many files as the k-value we were given
                File[] files = new File[k * 2];

                // Populating the file array with temporary files that will be deleted on exit
                for (int j = 0; j < (k * 2); j += 2) {
                    //在默认临时文件目录中创建一个空文件，使用给定前缀和后缀生成其名称。
                    files[j] = File.createTempFile("Merge-", ".txt");
                    //在JVM退出时删除文件
                    files[j].deleteOnExit();

                    //在默认临时文件目录中创建一个空文件，使用给定前缀和后缀生成其名称。
                    files[j + 1] = File.createTempFile("Merge-", ".txt");
                    //在JVM退出时删除文件
                    files[j + 1].deleteOnExit();
                }

                // Populating the writers array with elements linked to the first k many temporary files in our array
                for (int i = 0; i < k; i++) {
                    // The append flag is set to true so no data is overwritten
                    writers[i] = new PrintWriter(new BufferedWriter(new FileWriter(files[i], true)));
                }

                // IF NOT USING END-OF-RUN MARKERS:                
                // Adding each line from the input file to the current temporary file until we reach the end of that run
                int n = 0;
                String inputLine;
                String previousLine = null;
                while ((inputLine = br.readLine()) != null) {
                    // Checking whether we have reached the end of a run
                    if (previousLine != null && inputLine.compareTo(previousLine) <= 0) {
                        // If so increment n (the index of the temporary file)
                        n++;
                        // If n is now outside of the first k many files in the file array, reset n to 0
                        if (n == k) {
                            n = 0;
                        }
                    }
                    // Then adding the line as normal to the temporary file at array index n
                    writers[n].println(inputLine);
                    // Storing the current line so we can compare against it the next time
                    previousLine = inputLine;
                }

                // IF USING END-OF-RUN MARKERS:
                /*// Adding each line from the input file to the current temporary file until we reach the end of that run
                int n = 0;
                String inputLine;
                while ((inputLine = br.readLine()) != null) {
                    // Checking whether we have reached the end-of-line marker
                    if (inputLine.equals("][][][][")) {
                        // If so increment n (the index of the temporary file)
                        n++;
                        // If n is now outside of the first k many files in the file array, reset n to 0
                        if (n == k) {
                            n = 0;
                        }
                    }
                    // Otherwise adding the line as normal to the temporary file at array index n
                    else {
                        writers[n].println(inputLine);
                    }
                }*/

                // Closing the inputfile reader and all writers in the writer array
                br.close();
                for (int i = 0; i < k; i++) {
                    writers[i].close();
                }

                // We don't know whether the sorted file will be file 0 or file k in the files array, so we can check
                // whether both of the preceding files are empty, which if true means all the data is sorted in either
                // file 0 or file k. Until then, keep looping.
                boolean oddNumPasses = true;
                int totalPasses = 0;
                while (!(files[1].length() == 0 && files[k + 1].length() == 0)) {
                    // If we are in an odd number(奇数) of passes, we will have files 0 - k as our input files and k - k*2
                    // as our output files, otherwise we will have files k - k*2  as our input files and 0 - k*2 as
                    // our output files, so we need this flag to check
                    if (oddNumPasses) {
                        // 奇数 Creating a new minheap with a max capacity of the number of files we have (k)
                        MinHeap minHeap = new MinHeap(k);
                        // Adding the files if they are not empty
                        for (int i = 0; i < k; i++) {
                            if (files[i].length() != 0) {
                                minHeap.addFile(files[i]);
                            }
                        }

                        // Checking that the input files are not ALL empty
                        boolean inputFilesNotEmpty = true;
                        int passes = k;
                        while (inputFilesNotEmpty) {
                            // The output file starts at k and increments after each pass, if it ever reaches k*2 it
                            // resets to k
                            if (passes == k * 2) {
                                passes = k;
                            }
                            // Creating a new pass and incrementing the pass counter by 1
                            minHeap.createPass(files[passes]);
                            totalPasses++;

                            // Assuming the input files are empty, check the length of each. If any are not empty, set
                            // the flag to true again
                            inputFilesNotEmpty = false;
                            for (int i = 0; i < k; i++) {
                                if (files[i].length() != 0) {
                                    inputFilesNotEmpty = true;
                                }
                            }
                            // Incrementing the pass file counter so we will write to the next file in the array
                            passes++;
                        }
                        oddNumPasses = false;
                    } else {
                        // 偶数 Creating a new minheap with a max capacity of the number of files we have (k)
                        MinHeap minHeap = new MinHeap(k);
                        // Adding the files if they are not empty
                        for (int i = k; i < k * 2; i++) {
                            if (files[i].length() != 0) {
                                minHeap.addFile(files[i]);
                            }
                        }

                        // Checking that the input files are not ALL empty
                        boolean inputFilesNotEmpty = true;
                        int passes = 0;
                        while (inputFilesNotEmpty) {
                            // The output file starts at 0 and increments after each pass, if it ever reaches k it
                            // resets to 0
                            if (passes == k) {
                                passes = 0;
                            }
                            // Creating a new pass and incrementing the pass counter by 1
                            minHeap.createPass(files[passes]);
                            totalPasses++;

                            // Assuming the input files are empty, check the length of each. If any are not empty, set
                            // the flag to true again
                            inputFilesNotEmpty = false;
                            for (int i = k; i < k * 2; i++) {
                                if (files[i].length() != 0) {
                                    inputFilesNotEmpty = true;
                                }
                            }
                            // Incrementing the pass file counter so we will write to the next file in the array
                            passes++;
                        }
                        oddNumPasses = true;
                    }
                } // end k-way-merge

                if (files[0].length() != 0) {
                    // Checking whether the sorted data is stored in the file at array index 0, and if so renaming it to the
                    // sorted filename we created
                    files[0].renameTo(sortedFile);
                } else if (files[k].length() != 0) {
                    // Checking whether the sorted data is stored in the file at array index k, and if so renaming it to the
                    // sorted filename we created
                    files[k].renameTo(sortedFile);
                } else {
                    // The program should never go into here if the logic above is sound, but catching the error just in case
                    System.out.println("ERROR: sorted file not found");
                }

                // Printing to standard error the total number of passes required to sort the data
                System.err.println("Total Passes: " + Integer.toString(totalPasses));
            } catch (Exception ex) {
                // Catching the exception of being unable to parse the argument at index 0 to an int (and any other
                // exceptions)
                System.out.println("Exception Thrown! " + ex.toString());
                return;
            }
        }
    }
}


